package com.company.剑指offer每日刷题.普通版;

import sun.reflect.generics.tree.Tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 面试题32 - I. 从上到下打印二叉树
 * 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

 * 例如:
 * 给定二叉树: [3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回：
 *
 * [3,9,20,15,7]
 * 提示：
 *
 * 节点总数 <= 1000
 * */
public class LevelOrder {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    /**
     * 方法：队列遍历二叉树
     * 思路：
     *  初始条件：从根节点开始，将节点加入队列中，
     *  第一步：队列中获取一个节点，访问该节点的值
     *  第二步：将其所有存在的子节点，从左到右的顺序，加入队列尾部。
     *  重复一二步骤，直到队列为空。
     * */
    public int[] levelOrder(TreeNode root) {
        if(root == null){
            return new int[0];
        }
        int [] temp = new int[1000];
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        int i=0;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            temp[i++] = node.val;
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }
        return Arrays.copyOf(temp,i);
    }
}
